class Solution { 	//leetcode931——下降路径最小和
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        //创建DP表
        int n=matrix.size();
        vector<vector<int>> dp(n+1,vector<int>(n+2,INT_MAX));
        //初始化
        for(auto& e:dp[0]){
            e=0;
        }
        //状态表示：dp[i][j]为，在I,J位置上，最小的下降路径
        //状态转移方程:dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+matrix[i][j]
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1])+matrix[i-1][j-1];
            }
        }
        int ret=dp[n][0];
        for(auto e:dp[n]){
            ret=ret>e?e:ret;
        }
        return ret;
    }
};